import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-09-25
 * Time: 22:31
 */
//class Base{
//    public Base(String s){
//        System.out.print("B");
//    }
//}
//public class Exam925 extends Base{
//    public Exam925(String s) {
//        super(s);
//        System.out.print("D");
//    }
//    public static void main(String[] args){
//        new Exam925("C");
//    }
//}
public class Exam925 {
    public static int MoreThanHalfNum_Solution3(int[] numbers) {
        int cond = 0;
        int cnt = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(cnt == 0) {
                cond = numbers[i];
                cnt++;
            } else {
                if(cond == numbers[i]) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        cnt = 0;
        for (int n :
                numbers) {
            if (n == cond) {
                cnt++;
            }
        }
        if(cnt > numbers.length / 2) {
            return cond;
        }
        return 0;
    }
    /**
     * sort
     * @param numbers
     * @return
     */
    public int MoreThanHalfNum_Solution1 (int[] numbers) {
        Arrays.sort(numbers);
        int num = numbers[numbers.length / 2];
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(numbers[i] == num) {
                count++;
            }
        }
        if(count > numbers.length / 2) {
            return num;
        }
        return 0;
    }

    /**
     * hash
     * @param numbers
     * @return
     */
    public int MoreThanHalfNum_Solution2 (int[] numbers) {
        // write code here
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if(!hashMap.containsKey(numbers[i])) {
                hashMap.put(numbers[i], 1);
            } else {
                hashMap.put(numbers[i], hashMap.get(numbers[i]) + 1);
            }
            if(hashMap.get(numbers[i]) > numbers.length / 2) {
                return numbers[i];
            }
        }
        return 0;
    }
    public static int MoreThanHalfNum_Solution0 (int[] numbers) {
        int count = 0;
        int max = 0;
        int ans = 50001;
        for (int i = 0; i < numbers.length - 1; i++) {
            if(numbers[i] == numbers[i + 1]) {
                count++;
                if(max < count) {
                    ans = numbers[i];
                }
            } else {
                if(max < count) {
                    max = count;
                }
                count = 0;
            }
        }
        return ans;
    }
    //[1,2,3,2,2,2,5,4,2]
    public static void main0(String[] args) {
        int[] num = new int[]{2,2,2,2,2,1,3,4,5};
        System.out.println(MoreThanHalfNum_Solution3(num));

    }
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int flag = 0;
        int count = 0;
        int max = 0;
        int index = 0;
        int ansIndex = 0;
        for (char c :
                str.toCharArray()) {
            if(Character.isDigit(c)) {
                flag = 1;
                count++;
            } else {
                if(flag == 1) {
                    if(max < count) {
                        max = count;
                        ansIndex = index - count;
                    }
                    flag = 0;
                    count = 0;
                }
            }
            index++;
        }
        if(max < count) {
            max = count;
            ansIndex = index - count;
        }
        for (int i = ansIndex; i < ansIndex + max; i++) {
            System.out.print(str.toCharArray()[i]);
        }
    }
}
